package group.anagrams;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @Time 2019/12/29
 * @author 王光浩
 * @Need 给一组字符串，对字符串中的同字母不同构造的字符串进行分组，将所这样的字符串放在一组。
 * @Thinking 使用hashMap。key为排序后的字符串，value当前字符串应当存储的位置。
 *           思路：首先设计一个保存结果的ArrayList集合，然后创建一个HashMap，遍历数组，首先将字符串进行排序如果
 *                 在HashMap中存在排序后的字符串，则获取对应的value，然后在ArrayList集合中使用value找到对应的应当
 *                 存储的位置，将排序之前的字符串存储在ArrayList中，否则将排序后的字符串加入到HashMap中同时加入到
 *                 ArrayList中。
 *           复杂度分析：时间复杂度O（n*mlog(m)）,空间复杂度O（n*m）,n为字符串数组长度，m为字符串长度，外部遍历时间为
 *                 O（n），内部对每一个字符串进行排序的时间为mlog(m)
 */
public class MyMethodOne { 
	public List<List<String>> groupAnagrams(String[] strs) {
		Map<String,Integer> hashMap=new HashMap<String,Integer>();
		List<List<String>> result=new ArrayList<List<String>>();
		int index=0;                 //统计分组个数
		String tem;
		int len=strs.length;
		//遍历字符串数组
		for(int i=0;i<len;i++) {
			tem=this.sort(strs[i]);
			if(hashMap.containsKey(tem)) {
				result.get(hashMap.get(tem)).add(strs[i]); //将同构元素加入结果中
				continue;
			}
			//不存在就将其加入HashMap中,同时在result中创建一个新的分组，并将该元素加入分组中
			hashMap.put(tem, index++);
			List<String> linked=new LinkedList<String>();
			linked.add(strs[i]);
			result.add(linked);
		}
		//返回结果
		return result;
    }
	/**对字符串进行排序，并将结果返回*/
	private String sort(String tem) {
		int[] ascii=new int[tem.length()];
		int len=tem.length();
		for(int i=0;i<len;i++) {
			ascii[i]=tem.charAt(i);
		}
		Arrays.sort(ascii);
		StringBuilder result=new StringBuilder();
		for(int i=0;i<len;i++) {
			result.append((char)(ascii[i]));
		}
		return result.toString();
	}
}
